package LeetCode.LC5;

/**
 * @author corn
 * @create 2020-07-25-21:12
 */

/**
 * 5. 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 */
public class LongestPalindrome {
    public static void main(String[] args) {
        Solution sol = new Solution();
        String s = "abcbddb";
        System.out.println(sol.longestPalindrome(s));
    }

}
class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0){
            return "";
        }
        //保存回文数的开始及结尾
        int[] index = new int[2];//(0,0)
        for (int i = 0; i < s.length(); i++) {
            //回文数为奇数
            Palindrome(s,i,i,index);
            //回文数为偶数
            Palindrome(s,i,i+1,index);
        }
        return s.substring(index[0],index[1]+1);
    }
    public void Palindrome(String s,int start,int end,int[] index){
        while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            start--;
            end++;
        }
        //判断找到的回文数与已有的回文数(end,start)
        if((end-start-2) > index[1]-index[0]){
            index[0] = start+1;
            index[1] = end-1;
        }
    }
}
